## 快排-微软
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

# 使用示例
array = [3, 6, 8, 10, 1, 2, 1]
sorted_array = quick_sort(array)
print(sorted_array)


## 迪杰斯特拉算法
import heapq

def dijkstra(graph, start):
    # 初始化距离字典，将所有节点的距离设为无穷大，起始点到自己的距离设为0
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0

    # 使用优先队列（堆）来存储待处理的节点
    priority_queue = [(0, start)]

    while priority_queue:
        # 弹出当前距离最小的节点
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # 如果这个距离已经大于字典中记录的距离，则忽略这个节点
        if current_distance > distances[current_vertex]:
            continue

        # 遍历当前节点的邻居
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # 如果通过当前节点到达邻居的距离更短，则更新距离并加入优先队列
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 使用示例
# 图以邻接表的形式表示，其中键是节点，值是字典，字典的键是邻居节点，值是边的权重
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

start_node = 'A'
print(dijkstra(graph, start_node))


